package com.lee.algorithm.tree;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.stream.Collectors;

public class LeetCode112 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(3);
        TreeNode treeNode3 = new TreeNode(6);
        TreeNode treeNode4 = new TreeNode(2);
        TreeNode treeNode5 = new TreeNode(8);
        TreeNode treeNode6 = new TreeNode(2);
        TreeNode treeNode7 = new TreeNode(10);
        TreeNode treeNode8 = new TreeNode(4);
        TreeNode treeNode9 = new TreeNode(5);

        root.setLeft(treeNode2);
        root.setRight(treeNode3);

        treeNode2.setLeft(treeNode4);
        treeNode2.setRight(treeNode5);

        treeNode3.setLeft(treeNode6);

        treeNode4.setRight(treeNode7);

        treeNode5.setLeft(treeNode8);

        treeNode6.setRight(treeNode9);

        List<List<Integer>> lists = pathSum(root, 16);
        System.out.println(lists);

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public void setLeft(TreeNode left) {
            this.left = left;
        }

        public void setRight(TreeNode right) {
            this.right = right;
        }

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 给你二叉树的根节点 root  和一个表示目标和的整数 targetSum。
     * 判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum。
     * 如果存在，返回 true ；否则，返回 false 。
     * <p>
     * 叶子节点 是指没有子节点的节点
     * 就是找路径
     *
     * @param root
     * @return
     */
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        int pathSum = 0;
        List<Integer> result = new ArrayList<>();
        hasPathSum(root, pathSum, result);
        return result.contains(10);
    }

    public static void hasPathSum(TreeNode root, Integer pathSum, List<Integer> result) {
        pathSum += root.val;
        if (root.left == null && root.right == null) {
            result.add(pathSum);
            return;
        }
        if (root.left != null) {
            hasPathSum(root.left, pathSum, result);
        }
        if (root.right != null) {
            hasPathSum(root.right, pathSum, result);
        }
    }


    public static List<String> allPath(TreeNode root) {
        ArrayList<String> allPath = new ArrayList<>();
        if (root == null) {
            return allPath;
        }
        StringBuilder path = new StringBuilder();
        getAllPath(root, allPath, path);
        return allPath;
    }

    public static void getAllPath(TreeNode root, List<String> allPath, StringBuilder path) {
        path.append(root.val);
        if (root.left == null && root.right == null) {
            allPath.add(path.toString());
            return;
        }
        if (root.left != null) {
            getAllPath(root.left, allPath, path);
            path.deleteCharAt(path.length() - 1);
        }
        if (root.right != null) {
            getAllPath(root.right, allPath, path);
            path.deleteCharAt(path.length() - 1);
        }
    }


    /**
     * 找到所有和 = targetSum 的路径
     *
     * @param root
     * @param targetSum
     * @return
     * @author 博客园 @ 青石路
     */
    public static List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> allPath = new ArrayList<>();
        findPath(root, allPath, new ArrayList<>(), 0, targetSum);
        return allPath;
    }

    /**
     * 找到所有和 = targetSum 的路径
     * 两个注意点：1、为什么不直接将 curPath 添加到 allPath，而是 copy 一份之后再添加到 allPath
     *           2、为什么要回溯
     *
     * @param node
     * @param allPath
     * @param curPath
     * @param sum
     * @param targetSum
     * @author 博客园 @ 青石路
     */
    public static void findPath(TreeNode node, List<List<Integer>> allPath, List<Integer> curPath, int sum, int targetSum) {
        sum = sum + node.val;
        curPath.add(node.val);
        if (node.left == null && node.right == null) {  //  一条完整路径走完
            if (sum == targetSum) {
                // 一定要重新 copy 一份，curPath 存在回溯的过程，元素会变化
                ArrayList<Integer> path = new ArrayList<>(curPath);
                allPath.add(path);
            }
            return;
        }
        if (node.left != null) {
            findPath(node.left, allPath, curPath, sum, targetSum);
            // 回溯，node.left 已经在 curPath 中了，需要回到 node.left 不在 curPath 中的时候
            curPath.remove(curPath.size() - 1);
        }
        if (node.right != null) {
            findPath(node.right, allPath, curPath, sum, targetSum);
            // 回溯，node.right 已经在 curPath 中了，需要回到 node.right 不在 curPath 中的时候
            curPath.remove(curPath.size() - 1);
        }
    }
}















